1. Field
The present disclosure relates to computer systems and methods in which data resources are shared among data consumers while preserving data integrity and consistency relative to each consumer. More particularly, the disclosure concerns a mutual exclusion mechanism known as “read-copy update.”
2. Description of the Prior Art
By way of background, read-copy update (also known as “RCU”) is a mutual exclusion technique that permits shared data to be accessed for reading without the use of locks, writes to shared memory, memory barriers, atomic instructions, or other computationally expensive synchronization mechanisms, while still permitting the data to be updated (modify, delete, insert, etc.) concurrently. The technique is well suited to both uniprocessor and multiprocessor computing environments wherein the number of read operations (readers) accessing a shared data set is large in comparison to the number of update operations (updaters), and wherein the overhead cost of employing other mutual exclusion techniques (such as locks) for each read operation would be high. By way of example, a network routing table that is updated at most once every few minutes but searched many thousands of times per second is a case where read-side lock acquisition would be quite burdensome.
The read-copy update technique implements data updates in two phases. In the first (initial update) phase, the actual data update is carried out in a manner that temporarily preserves two views of the data being updated. One view is the old (pre-update) data state that is maintained for the benefit of read operations that may have been referencing the data concurrently with the update. The other view is the new (post-update) data state that is seen by operations that access the data following the update. In the second (deferred update) phase, the old data state is removed following a “grace period” that is long enough to ensure that the first group of read operations will no longer maintain references to the pre-update data. The second-phase update operation typically comprises freeing a stale data element to reclaim its memory. In certain RCU implementations, the second-phase update operation may comprise something else, such as changing an operational state according to the first-phase update.
FIGS. 1A-1D illustrate the use of read-copy update to modify a data element B in a group of data elements A, B and C. The data elements A, B, and C are arranged in a singly-linked list that is traversed in acyclic fashion, with each element containing a pointer to a next element in the list (or a NULL pointer for the last element) in addition to storing some item of data. A global pointer (not shown) is assumed to point to data element A, the first member of the list. Persons skilled in the art will appreciate that the data elements A, B and C can be implemented using any of a variety of conventional programming constructs, including but not limited to, data structures defined by C-language “struct” variables. Moreover, the list itself is a type of data structure.
It is assumed that the data element list of FIGS. 1A-1D is traversed (without locking) by multiple readers and occasionally updated by updaters that delete, insert or modify data elements in the list. In FIG. 1A, the data element B is being referenced by a reader r1, as shown by the vertical arrow below the data element. In FIG. 1B, an updater u1 wishes to update the linked list by modifying data element B. Instead of simply updating this data element without regard to the fact that r1 is referencing it (which might crash r1), u1 preserves B while generating an updated version thereof (shown in FIG. 1C as data element B′) and inserting it into the linked list. This is done by u1 acquiring an appropriate lock (to exclude other updaters), allocating new memory for B′, copying the contents of B to B′, modifying B′ as needed, updating the pointer from A to B so that it points to B′, and releasing the lock. In current versions of the Linux® kernel, pointer updates performed by updaters can be implemented using the rcu_assign_pointer ( ) primitive. As an alternative to locking during the update operation, other techniques such as non-blocking synchronization or a designated update thread could be used to serialize data updates. All subsequent (post update) readers that traverse the linked list, such as the reader r2, will see the effect of the update operation by encountering B′ as they dereference B's pointer. On the other hand, the old reader r1 will be unaffected because the original version of B and its pointer to C are retained. Although r1 will now be reading stale data, there are many cases where this can be tolerated, such as when data elements track the state of components external to the computer system (e.g., network connectivity) and must tolerate old data because of communication delays. In current versions of the Linux® kernel, pointer dereferences performed by readers can be implemented using the rcu_dereference ( ) primitive.
At some subsequent time following the update, r1 will have continued its traversal of the linked list and moved its reference off of B. In addition, there will be a time at which no other reader task is entitled to access B. It is at this point, representing an expiration of the grace period referred to above, that u1 can free B, as shown in FIG. 1D.
FIGS. 2A-2C illustrate the use of read-copy update to delete a data element B in a singly-linked list of data elements A, B and C. As shown in FIG. 2A, a reader r1 is assumed be currently referencing B and an updater u1 wishes to delete B. As shown in FIG. 2B, the updater u1 updates the pointer from A to B so that A now points to C. In this way, r1 is not disturbed but a subsequent reader r2 sees the effect of the deletion. As shown in FIG. 2C, r1 will subsequently move its reference off of B, allowing B to be freed following the expiration of a grace period.
In the context of the read-copy update mechanism, a grace period represents the point at which all running tasks (e.g., processes, threads or other work) having access to a data element guarded by read-copy update have passed through a “quiescent state” in which they can no longer maintain references to the data element, assert locks thereon, or make any assumptions about data element state. By convention, for operating system kernel code paths, a context switch, an idle loop, and user mode execution all represent quiescent states for any given CPU running non-preemptible code (as can other operations that will not be listed here). The reason for this is that a non-preemptible kernel will always complete a particular operation (e.g., servicing a system call while running in process context) prior to a context switch.
In FIG. 3, four tasks 0, 1, 2, and 3 running on four separate CPUs are shown to pass periodically through quiescent states (represented by the vertical bars). The grace period (shown by the dotted vertical lines) encompasses the time frame in which all four tasks that began before the start of the grace period have passed through one quiescent state. If the four tasks 0, 1, 2, and 3 were reader tasks traversing the linked lists of FIGS. 1A-1D or FIGS. 2A-2C, none of these tasks having reference to the old data element B prior to the grace period could maintain a reference thereto following the grace period. All post grace period searches conducted by these tasks would bypass B by following the updated pointers created by the updater.
RCU implementations may use a combining tree to track quiescent states, with bitmasks at each level of the tree indicating which CPU's quiescent states are required in order to end a grace period. These bits are set at the beginning of each RCU grace period and cleared by CPUs when they pass through quiescent states. This is known as hierarchical RCU. In hierarchical RCU implementations that support CPU hotplugging, additional bitmasks are provided at each level to advise RCU which CPU's are offline, and whose quiescent states are therefore not required to end a grace period. When CPU hotplug events occur, these bits are set or cleared to respectively indicate CPU online or offline status.
In current versions of the Linux® kernel, the RCU combining tree used for quiescent state tracking is implemented using an rcu_state structure that contains a tree of rcu_node structures embedded as a linear array. FIG. 4 illustrates an example two-level tree hierarchy that includes two bottom-level leaf rcu_node structures and a single top level root rcu_node structure. In a larger system with many CPUs, the combining tree could be expanded to include one or more additional levels of rcu_node structures.
The qsmi bitmasks in FIG. 4 represents each rcu_node structure's ->qsmaskinit bitmask field indicating which CPUs are online or offline. The qsm bitmasks represent each rcu_node structure's ->qsmask bitmask field indicating which CPUs need to report a quiescent state before the current grace period can end. The root rcu_node structure in FIG. 4 is associated with two lower level leaf rcu_node structures. The root rcu_node structure's ->qsmaskinit and ->qsmask fields thus have two bits apiece, one for each of the two leaf rcu_node structures that report to it.
Each leaf rcu_node structure in FIG. 4 is associated with a two CPUs, each of which is represented by a corresponding per-CPU rcu_data structure. The leaf rcu_node structure's ->qsmaskinit and ->qsmask fields thus have two bits apiece, one for each of the two rcu_data structures that report to it. Among other thing, the rcu_data structures are used to maintain certain per-CPU RCU data, such as lists of RCU callbacks.
The CPUs in FIG. 4 periodically access their assigned leaf rcu_node structure to record RCU quiescent states by clearing their respective bits in the leaf rcu_node structure's ->qsmask field. When all of a leaf rcu_node structure's CPUs have passed through a quiescent state (and assuming the leaf rcu_node structure is not tracking any blocked RCU reader tasks), the last CPU to clear its bit in the leaf rcu_node structure's ->qsmask field propagates this state to the root rcu_node structure and clears a bit in the latter's ->qsmask field that corresponds to the leaf rcu_node structure. Or, if there are more than two levels in the combining tree, a bit will be cleared in the ->qsmask field of an rcu_node structure at the next higher level of the tree. Eventually, all of the root rcu_node structure's ->qsmask bits will cleared, at which point the current grace period may end.
The CPU's in FIG. 4 also periodically access their assigned leaf rcu_node structure to record CPU hotplug events by either setting or clearing their respective bits in the leaf rcu_node structure's ->qsmaskinit field. If all of the CPUs associated with a leaf rcu_node structure go offline (and assuming the leaf rcu_node structure is not tracking any blocked RCU reader tasks), the last CPU to clear its bit in the leaf rcu_node structure's ->qsmaskinit field bit propagates this state to the root rcu_node structure and clears a bit in the latter's ->qsmaskinit field that corresponds to the leaf rcu_node structure. Or, if there are more than two levels in the combining tree, a bit will be cleared in the ->qsmaskinit field of an rcu_node structure at the next higher level of the tree. Ultimately, by the time the current RCU grace period ends, the ->qsmaskinit field in the root rcu_node structure will have some of its bits cleared to reflect the fact that there are offline CPUs in the system. In order to avoid waiting for quiescent states from these online CPUs during the next RCU grace period, initialization of the new RCU grace period includes copying the ->qsmaskinit field to the ->qsmask field in each rcu_node structure of the combining tree. The new RCU grace period will thus only wait on CPUs that were online at the start of that grace period.
FIG. 4 shows a newly initialized grace period following the bitmask copying operation. As would be expected, the values of the ->qsmask and qsmaskinit fields are identical. The leftmost leaf rcu_node structure's fields show CPU0 online (qsmi) and being waited on (qsm) and CPU1 offline and not being waited on. Similarly, the rightmost rcu_node structure shows both CPU2 and CPU3 online and being waited on. The root rcu_node structure shows that each of the leaf rcu_node structures have at least one CPU that is online and being waited on.
An additional complication is posed by preemptible versions of RCU, where tasks can be preempted while running in an RCU read-side critical section. For example, FIG. 5 illustrates a scenario where Tasks A and B are preempted while running on CPU0, and then CPU0 goes offline. Although RCU does not need to wait on anything further from CPU0 and CPU1 in order to end the current grace period, it still needs to wait on Tasks A and B. To handle this situation, tasks A and B are queued on an rcu_node field called ->blkd_tasks, represented by the b tags on the leaf rcu_node structures. The leftmost leaf rcu_node structure's ->qsmask and ->qsmaskinit fields are both “0 0,” indicating that RCU need not wait on the now-offline CPU0 and CPU1, but the leftmost ->qsmask and ->qsmaskinit fields in the root rcu_node structure are both set to “1 1” to indicate that RCU still needs to wait on the tasks on the leftmost leaf rcu_node structure's ->blkd_tasks list. Propagation of the ->qsmask and ->qsmaskinit field state of the leftmost rcu_node structure to the root rcu_node structure is deferred until these tasks have completed and the ->blkd_tasks list is cleared.
Synchronization between RCU grace-period initialization and CPU hotplug operations (online and offline) is important. RCU grace-period initialization typically traverses the rcu_node tree breadth-first, from the root toward the leaves, copying the ->qsmaskinit fields to the ->qsmask fields in the rcu_node structures at each level. In contrast, CPU hotplug operations typically modify the ->qsmaskinit fields from the leaves to the root, setting bits in the ->qsmaskinit fields to note a newly onlined CPU and clearing them to note a newly offlined CPU. Allowing grace-period initialization to proceed concurrently with CPU hotplug bit manipulations can easily lead to confusion. For example, grace period initialization might handle the root rcu_node structure before a concurrent CPU hotplug operation reaches the root, and the CPU hotplug operation might clear a CPU's bit in the ->qsmaskinit field of one of the leaf rcu_node structures before grace period initialization reaches that leaf rcu_node structure.
An example of this is shown in FIGS. 6A-6C. FIG. 6A shows the rcu_state structure at the end of an old grace period and prior to the initialization of a new grace period. CPU0 is online and CPU1 is offline, such that the ->qsmaskinit field in the leftmost leaf rcu_node structure is “1 0.” The ->qsmask field in the leftmost leaf rcu_node structure is “0 0” because these bits were cleared during the old grace period and the new grace period has yet to be initialized. The ->qsmask field in the rightmost leaf rcu_node structure is the same, but its ->qsmaskinit field is “1 1” due to both CPU2 and CPU3 being online. In the root rcu_node structure, the ->qsmaskinit field is “1 1” to indicate there is at least one online CPU associated with each leaf rcu_node structure. The ->qsmask field in the root rcu_node structure is “0 0” because these bits were cleared during the old grace period and initialization for the new grace period has not yet started.
FIG. 6B shows the rcu_state structure after RCU grace period initialization has processed the root rcu_node structure but not the leaf rcu_node structures, and after CPU0 has gone offline and the CPU hotplug offlining operation has processed the ->qsmaskinit field in the leftmost leaf rcu_node structure, but not in the root rcu_node structure. The grace period initialization operation has copied the ->qsmaskinit field in the root rcu_node structure, whose value is “1 1,” to the root rcu_node structure's ->qsmask field, such that its value changes from “0 0” (as in FIG. 6A) to “1 1.” The CPU hotplug offlining operation has changed the ->qsmaskinit field in the leftmost leaf rcu_node structure from “1 0” (as in FIG. 6A) to “0 0” to reflect the offlining of CPU0.
FIG. 6C shows the rcu_state structure after RCU grace period initialization has processed the leaf rcu_nodes structures, and the CPU hotplug offlining operation has processed the ->qsmaskinit field in the root rcu_node structure. The grace period initialization operation has copied the ->qsmaskinit fields in the leaf rcu_node structures to the ->qsmask fields in those structures. In the leftmost leaf rcu_node structure, the ->qsmask field is still “0 0,” and in the rightmost leaf rcu_node structure the ->qsmask field changes from “0 0” to “1 1.” The CPU hotplug offlining operation has changed the ->qsmaskinit field in the root rcu_node structure from “1 1” to “0 0” in order to reflect the fact that the leftmost leaf rcu_node structure no longer has any online CPUs.
It will be appreciated that the condition of the rcu_state structure in FIG. 6C is problematic. Because CPU0 and CPU1 are both offline, the ->qsmask bit in the root rcu_node structure corresponding to the leftmost leaf rcu_node structure will never be cleared. Even if one of the offline CPUs were to inexplicably attempt to record a quiescent state, its ->qsmask bit in the leftmost leaf rcu_node structure is already zero. This zero value would tell the CPU that RCU is not expecting a quiescent state from it for the current grace period, and would prevent it from looking further up the combining tree, where RCU is in fact expecting a quiescent state. The RCU grace period will therefore never end, resulting in out-of-memory (OOM) conditions or even system hangs. It should be noted that the same issue can arise if the grace period initialization proceeds from leaf to root, and the hotplug operation proceeds from root to leaf.
To prevent these OOMs and system hangs, RCU uses an ->onoff_mutex field (see FIGS. 6A-6C) in the rcu_state structure to provide a sleeplock that prevents RCU grace-period initialization from running concurrently with CPU hotplug's ->qsmaskinit manipulations. The ->onoff_mutex sleeplock prevents changes in RCU's CPU hotplug state while the combining tree is being initialized for a new grace period. Using a sleeplock allows RCU grace-period initialization to be preempted, which is critically important on large systems. For example, a system with 4096 CPUs running a Linux® kernel with default Kconfig settings may have an RCU combining tree containing no fewer than 261 rcu_node structures, which can take more than 200 microseconds to initialize. This latency is unacceptably large for a few important applications, hence the need for RCU grace period initialization preemptability.
Unfortunately, use of the ->onoff_mutex sleeplock means that CPU hotplug bit operations on the ->qsmaskinit fields must be carried out in a preemptible context, which rules out performing CPU-offlining from the portion of the idle loop that offline CPUs go to in order to be powered off. It is highly desirable to instead carry this operation out from that portion of the idle loop, as this would eliminate RCU's current uncertainty as to exactly when a given CPU has gone offline. RCU currently assumes that it will take no longer than one jiffy (i.e., one tick of the system interrupt timer) for the offlining to complete, which is not an optimal approach. In addition, in virtualized settings, it is not unusual for a hypervisor to preempt a guest OS for far longer than on jiffy. In such situations, RCU will assume that the CPU has already gone offline when in fact it has not yet done so. Because the outgoing CPU will pass through the scheduler, which uses RCU, this can cause the scheduler to access freed data on the outgoing CPU. Applicant submits that it would be better for RCU to know exactly when a given CPU went offline, without arbitrarily chosen one jiffy timeout periods.
There is therefore a need for some mechanism that allows RCU grace period initialization to be preempted, while still properly accounting for CPU hotplug events.